//解法1
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp;
        dp.resize(n+1);
        dp[0]=dp[1]=0;
        for(int i=2;i<=n;i++)
        {
            dp[i] = min((dp[i-1]+cost[i-1]),(dp[i-2]+cost[i-2]));
        }
        return dp[n];
    }
};

//解法2
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp;
        dp.resize(n);
        dp[n-1]=cost[n-1];
        dp[n-2]=cost[n-2];
        for(int i=n-3;i>=0;i--)
        {
            dp[i]=min((dp[i+1]+cost[i]),(dp[i+2]+cost[i]));
        }
        return min(dp[0],dp[1]);
    }
};